<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    var findAllConcatenatedWordsInADict = function (words) {
      let trie = new Trie();
      let ans = Array();
      // 按单词长度排列
      words.sort((a, b) => a.length - b.length);
      // 对单词数组每一项进行 dfs搜索 如果当前单词是连接词 
      // 也就是说 在当前 word 的某种方式的切片中 能满足每一个切片都存在 trie 中 那么就是连接词
      // 这里多了一点优化：记忆化数组 
      // 如果一个下标已经被访问过，则从该下标到末尾的部分一定不是由给定数组中的一个或多个非空单词组成（否则上次访问时已经可以知道当前单词是连接词），只有尚未访问过的下标才需要进行搜索。
      // 递归时会出现重复的处理。
      // 例如，如果存在单词a = b+c+d，b+c = e。那么在处理a时，可有两条路径成功，即b->c->d和e->d。
      // 那么d被搜索了两次！所以，此处考虑加入记忆化，对每一轮递归访问的起点下标进行标记。
      // 如果某一轮递归从一个已经被访问过的起点开始，那么直接返回。
      words.forEach(item => {
        if (!item) return;
        // 
        const visited = new Array(item.length).fill(false);
        // 如果深度优先搜索 在 trie 中都能找到当前的 word 的分块
        if (dfs(trie, item, 0, visited)) {
          ans.push(item);
        } else {
          // 没有在 trie 中找到 item 
          // 那么需要进行插入操作
          trie.insert(item);
        }
      })
      return ans;
    };

    // 在 trie 中找 word 的分块
    var dfs = function (trie, word, start, visited) {
      // 结束条件：如果传入的 word 已经没有了 表示这个路径上的 word 是可行的
      if (start == word.length) return true;
      // 如果之前已经遍历过 也就是说 之前已经尝试过把 start 的 char 加进去 但是回溯了 
      // 说明继续再走 start 这条路 是不行的 那么直接省去后面的重复操作
      if (visited[start]) return false;
      // 记录一下当前 start 是走过了的
      visited[start] = true;
      // 取出当前节点的下一层
      let nodes = trie.children;
      // 对 word 的每一个 char 进行遍历
      for (let i = start; i < word.length; i++) {
        // 获取 char 的值
        let char = word[i];
        // 取出 当前层的 char
        nodes = nodes[char]
        // 如果没有 那么结束
        if (!nodes) return false;
        // 如果 Trie 有当前遍历到的 word 的 char 并且 当前 char 是 Trie 中已经结束的子串
        // 就进入下一层（截取后面没有遍历到的 word）
        // 如果传入的 word 在后面每次都能找到 Trie 的节点
        if (nodes.isEnd && dfs(trie, word, i + 1, visited)) return true;
      }
      return false;
    }

    // 手动创建前缀树
    class Trie {
      // 节点之间通过 children 对象传递
      constructor() {
        this.children = {}
      }
      // 前缀树插入操作
      insert(word) {
        // 首先获取当前节点的下一层 children 节点
        let nodes = this.children;
        // 因为要插入一个 word 那么肯定是要进行 word 的每一个 char 的遍历
        for (let char of word) {
          // 如果下一层没找到 char 那么创建一个 index 为 char 节点 value 是空对象 的节点
          if (!nodes[char]) nodes[char] = {};
          // 进入下一层 且应该是 下一层 index 为 char 的 节点
          nodes = nodes[char];
        }
        // 循环结束 表示当前的这一层的这一个 index 是 char 的节点已经是 word 的最后一个 char 了
        // 将当前这一层 设置为 已经遍历完的 flag
        nodes.isEnd = true;
      }
    }
  </script>
</body>

</html>